#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define endl '\n'
const int N = 1e5 + 5;

int n, m;
int a[N];
int b[N << 1], num;
struct Q {
  char op;
  int x, y, z;
} q[N];
struct Node {
  int cnt;
  int ch[2];
} tr[N * 400];
#define cnt(p) tr[p].cnt
#define lc(p) tr[p].ch[0]
#define rc(p) tr[p].ch[1]
int newnode(int p) {
  static int tot = 0;
  ++tot;
  cnt(tot) = cnt(p);
  lc(tot) = lc(p);
  rc(tot) = rc(p);
  return tot;
}
void pushup(int p) { cnt(p) = cnt(lc(p)) + cnt(rc(p)); }
void update(int x, int d, int& p, int l, int r) {
  p = newnode(p);
  cnt(p) += d;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(x, d, lc(p), l, mid);
  else
    update(x, d, rc(p), mid + 1, r);
  // pushup
}
int query(int L, int R, int& p, int l, int r) {
  if (L <= l && R >= r) return cnt(p);
  int res = 0;
  int mid = (l + r) >> 1;
  if (L <= mid) res += query(L, R, lc(p), l, mid);
  if (R > mid) res += query(L, R, rc(p), mid + 1, r);
  return res;
}
int rt[N];
int lowbit(int x) { return x & -x; }
void update(int x, int val, int d) {
  for (int i = x; i <= n; i += lowbit(i)) {
    update(val, d, rt[i], 1, num);
  }
}
int query(int x, int val) {
  int res = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    res += query(1, val, rt[i], 1, num);
  }
  return res;
}
void build() { rep(i, 1, n) update(i, a[i], 1); }
int query(int x, int y, int k) {
  int l = 1, r = num;
  while (l <= r) {
    int mid = (l + r) >> 1;
    int cnt = query(y, mid) - query(x - 1, mid);
    if (cnt >= k)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return l;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m;
  rep(i, 1, n) cin >> a[i];
  rep(i, 1, m) {
    cin >> q[i].op;
    if (q[i].op == 'Q')
      cin >> q[i].x >> q[i].y >> q[i].z;
    else
      cin >> q[i].x >> q[i].y;
  }
  // discrete
  rep(i, 1, n) b[i] = a[i];
  num = n;
  rep(i, 1, m) if (q[i].op == 'C') b[++num] = q[i].y;
  sort(b + 1, b + num + 1);
  num = unique(b + 1, b + num + 1) - b - 1;
  rep(i, 1, n) a[i] = lower_bound(b + 1, b + num + 1, a[i]) - b;

  build();
  rep(i, 1, m) {
    if (q[i].op == 'Q') {
      cout << b[query(q[i].x, q[i].y, q[i].z)] << endl;
    } else {
      update(q[i].x, a[q[i].x], -1);
      a[q[i].x] = lower_bound(b + 1, b + num + 1, q[i].y) - b;
      update(q[i].x, a[q[i].x], 1);
    }
  }
  return 0;
}